class Solution {
    public boolean checkPartitioning(String s) {
        // 创建 dp 表、初始化、填表、返回值
        // 1、构建完整的dp表信息
        int n = s.length();
        char[] ss = s.toCharArray();
        boolean[][] dp = new boolean[n][n];

        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j >= i; j--) {
                if (ss[i] == ss[j]) {
                    if (i == j || i+1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
            }
        }

        // 2、枚举所有的分割点，判断是否为回文子串
        // 枚举时，得确保 [0, i-1]、[i, j]、[j+1, n-1]区间都得有值
        // 从而得出边界值(i-1 >= 0，因此 i>=1, j>=i, j+1 <= n-1，因此j<=n-2)
        for (int i = 1; i < n-1; i++) {
            for (int j = i; j < n-1; j++) {
                // 判断三个子串是否都回文
                if (dp[0][i-1] && dp[i][j] && dp[j+1][n-1]) {
                    return true;
                }
            }
        }

        return false;
    }
}